package datastructure.unionfind;

import java.util.*;

class 尽量减少恶意软件的传播_924_重做版 {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int length = graph.length;
        UF uf = new UF(length);
        for(int i = 0 ; i < length ; i++) {
            for(int j = i + 1; j < length; j++) {
                if(graph[i][j] == 1) uf.union(i, j);
            }
        }

        Arrays.sort(initial);
        int toBeRemove = initial[0];
        int curSize = 0;
        int[] virusCntUnderRoot = new int[length];
        // 每个根节点下有几个病毒  2个或者以上都没法减少 因为删除了自身 自身还是会感染
        for(int i : initial) {
            virusCntUnderRoot[uf.findRoot(i)] ++;
        }

        for(int i : initial) {
            int root = uf.findRoot(i);
            if(virusCntUnderRoot[root] > 1) {
                continue;
            }
            int size = uf.size[root];
            if(size>curSize) {
                toBeRemove = i;
                curSize = size;
            }
        }
        /*for(int i = 0; i< length; i++) {
         System.out.println(i + "--->" + uf.root[i] + "--->" + uf.size[i]);

        }*/

        return toBeRemove;
    }

    private class UF{
        int[] root;
        int[] size;

        public UF(int c){
            root = new int[c];
            size = new int[c];
            for(int i = 0; i < c; i ++) {
                root[i] = i;
                size[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootp = findRoot(p);
            int rootq = findRoot(q);
            if(rootp != rootq) {
                root[rootq] = rootp; // 根合并
                size[rootp] += size[rootq]; // root下的节点数量累加
            }
        }

        public int findRoot(int p) {
            if(root[p] == p) return p;
            return root[p] = findRoot(root[p]);
        }
    }
}


/**814
 * 题意为
 *      一开始不感染哪个初始节点列表中的节点  会使得整体被感染节点数最少
 * 转化为并查集问题
 *      若两个节点都在同一个连通分量中 一开始不感染其中一个节点 最终整个联通分量包括另一个节点也会受到感染
 *      问题转化为 对 连通图每个联通分量  若连通分量中只有一个初始节点    看哪个联通分量总节点最多
 */
public class 尽量减少恶意软件的传播_924 {


        public int minMalwareSpread(int[][] graph, int[] initial) {
            DSU dsu = new DSU(graph.length);
            for(int i = 0; i< graph.length; i++) {
                for(int j = i+ 1; j< graph.length; j++) {
                    if(graph[i][j] == 1) dsu.union(i, j);
                }
            }
            // initial 找对应的连通分量节点个数最大的
            Arrays.sort(initial);
            int size = 0;
            int index = -1;
            // 记录initial中 同一root出现次数  看两个点是不是一个连通分量
            int[] rootCnt = new int[graph.length];
            for(int i = 0; i < initial.length; i++) {
                int root = dsu.findRoot(initial[i]);
                rootCnt[root] += 1;
            }

            for(int i = 0; i < initial.length; i++) {
                int root = dsu.findRoot(initial[i]);
                // 有两个点在一个连通分量中  跳过
                if(rootCnt[root] > 1) {
                    continue;
                }
                int curSize = dsu.size[root];
                if(curSize > size) {
                    // 当前连通分量总点数最大
                    size = curSize;
                    index = initial[i];
                }
            }
            // 多个点在一个连通分量中  取最小的initial值
            return index == -1 ? initial[0] : index;

        }

    /**
     * Disjoint Set Union
     */
        private class DSU {
            // 记录每个节点的父节点
            private int[] root;
            // 连通分量的节点数量
            private int[] size;
            public DSU(int n) {
                root = new int[n];
                size = new int[n];
                for(int i = 0; i < n; i++) {
                    root[i] = i;
                }
                Arrays.fill(size, 1);
            }


            public void union(int p, int q) {
                int pRoot = findRoot(p);
                int qRoot = findRoot(q);
                if(pRoot != qRoot) {
                    root[qRoot] = pRoot;
                    size[pRoot] += size[qRoot];
                    findRoot(q);
                }
            }

            private int findRoot(int p) {
                if(root[p] == p) {
                    return p;
                }
                return root[p] = findRoot(root[p]);
            }
        }


    public static void main(String[] args) {
        尽量减少恶意软件的传播_924 a = new 尽量减少恶意软件的传播_924();
        int i = a.minMalwareSpread(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}, new int[]{0, 1});
        System.out.println();
   }

}
